package com.erbao.datastructurearithmetic.base;

import com.erbao.SwapUtil;
import com.erbao.datastructurearithmetic.RandomUtil;
import com.erbao.datastructurearithmetic.tyro.Class1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author CaoBaoYin
 * @since 22/2/23 09:13
 */
public class Class04 {

    public static void main(String[] args) {
        // new Class04().testMaxHeap2();
        new Class04().testHeapSort();
        /*MaxHeap maxHeap = new MaxHeap(100);
        maxHeap.push(85);
        maxHeap.push(19);
        maxHeap.push(79);
        maxHeap.push(3);
        maxHeap.push(4);
        maxHeap.push(33);
        System.out.println(maxHeap.check(0));*/
    }

    public void testHeapSort () {
        int times = 1000000;

        for (int i = 0; i < times; i++) {
            int[] originalArr = RandomUtil.lenRandomAndValueRandom(100, 100);
            // System.out.println(Arrays.toString(originalArr));
            heapSort(originalArr);
            if (! Class1.isSort(originalArr)) {
                System.out.println("bad");
                System.out.println(Arrays.toString(originalArr));
                break;
            }
        }

        System.out.println("nice");
    }

    public void heapSort (int[] arr) {
        if (arr == null || arr.length == 1) return;

        /*形成大根堆 N*logN */
        /*
        int[] temp = new int[arr.length];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        int heapSize = 0;
        for (int i : temp) {
            arr[heapSize] = i;
            heapInsert(arr, heapSize);
            heapSize += 1;
        }*/
        /*for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;*/
        for (int i = arr.length-1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        int heapSize = arr.length;

        /*出堆后堆化 N*logN */
        while (heapSize > 0) {
            SwapUtil.swap(arr, 0, --heapSize);
            heapify(arr, 0, heapSize);
        }
    }

    public void testMaxHeap2 () {
        int limit = 100;
        MaxHeap maxHeap = new MaxHeap(limit);
        int testTimes = 1000000;
        List<Integer> list = new ArrayList<>(limit);
        for (int i = 0; i < testTimes; i++) {
            double random = Math.random();
            try {
                if (random < 0.5) {
                    int value = RandomUtil.equalProbabilityInt(100);
                    maxHeap.push(value);
                    list.add(value);
                } else {
                    int heapValue = maxHeap.pop();
                    Collections.sort(list);
                    Integer listValue = list.remove(list.size()-1);
                    if (heapValue != listValue) {
                        System.out.println("值不等");
                        System.out.println(list);
                        System.out.println(maxHeap);
                        break;
                    }
                }
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }

        System.out.println("wonderful");
    }

    public void testMaxHeap () {
        MaxHeap maxHeap = new MaxHeap(100);
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            double random = Math.random();
            try {
                if (random < 0.5) {
                    maxHeap.push(RandomUtil.equalProbabilityInt(100));
                } else {
                    maxHeap.pop();
                }
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }

            System.out.println(maxHeap);

            if (! maxHeap.check(0)) {
                System.out.println("bad");
                return;
            }
        }

        System.out.println("wonderful");
    }

    private void heapInsert(int[] arr, int index) {
        /*只需要当前节点跟父节点做对比。比较次数为logN，即树的层级，N为节点个数
         * 其他子树都是之前插数据做过比较已经满足大根堆要求
         * 跳出循环条件：到达树的根结点；父节点大于或等于子节点*/
        while (arr[index] > arr[(index - 1)/2]) {// 子节点 大于 父节点
            SwapUtil.swap(arr, index, (index - 1)/2);//交换
            index = (index - 1)/2;//下一轮
        }
    }

    /**
     *
     * @param arr 存放堆数据的数组
     * @param index 从当前位置往下比较
     * @param heapSize 堆的大小，避免越界
     */
    private void heapify(int[] arr, int index, int heapSize) {
        /*从零开始做跟孩子做比较，直到叶子节点或者比较完不用交换了*/
        int leftChildIndex = (index << 1) | 1;
        while (leftChildIndex < heapSize) {//说明还有孩子结点

            int largerChildIndex = leftChildIndex;
            int rightChildIndex = leftChildIndex + 1;
            if (rightChildIndex < heapSize) {//有右孩子
                largerChildIndex = arr[leftChildIndex] > arr[rightChildIndex] ? leftChildIndex : rightChildIndex;
            }

            // 根结点要满足当前子树最大，如果不满足，需要交换
            if (arr[index] < arr[largerChildIndex]) {
                SwapUtil.swap(arr, index, largerChildIndex);
                index = largerChildIndex;
                leftChildIndex = (index << 1) | 1;
            } else {// 当前子树已经满足大根堆，不用再往下比较了
                break;
            }

        }
    }
}

/**
 * 大根堆,完全二叉树
 * 从左到右，从上到下依次存放
 */
class MaxHeap {
    /** 堆大小 */
    private int heapSize;
    /** 堆的最大容量 */
    private final int limit;
    private final int[] arr;

    /**
     * 校验是否满足大根堆
     * @param rootIndex 当前树父节点角标
     * @return true 满足大根堆
     */
    public boolean check (int rootIndex) {
        int leftIndex = (rootIndex << 1) | 1 ;
        if (leftIndex < heapSize) { // 存在左孩子
            int largerIndex = leftIndex;
            int rightIndex = leftIndex + 1;
            if (rightIndex < heapSize) {// 存在右孩子
                largerIndex = arr[leftIndex] > arr[rightIndex] ? leftIndex : rightIndex;
            }

            if (arr[rootIndex] < arr[largerIndex]) return false;

            boolean checkLeft = check(leftIndex);
            boolean checkRight = true;
            if (rightIndex < heapSize) {
                checkRight = check(rightIndex);
            }
            return checkLeft && checkRight;
        }
        return true;
    }

    public MaxHeap(int limit) {
        this.limit = limit;
        this.arr = new int[limit];
    }

    /**
     * 跟父节点比较，不行就交换
     * @param value 给的数字
     */
    public void push (int value) {
        if (heapSize == limit) {
            throw new RuntimeException("heap is full");
        }

        arr[heapSize] = value;//放入位置

        heapInsert(this.arr, heapSize++);//堆大小+1，并对位置数据和父节点对比
    }

    private void heapInsert(int[] arr, int index) {
        /*只需要当前节点跟父节点做对比。比较次数为logN，即树的层级，N为节点个数
        * 其他子树都是之前插数据做过比较已经满足大根堆要求
        * 跳出循环条件：到达树的根结点；父节点大于或等于子节点*/
        while (arr[index] > arr[(index - 1)/2]) {// 子节点 大于 父节点
            SwapUtil.swap(arr, index, (index - 1)/2);//交换
            index = (index - 1)/2;//下一轮
        }
    }

    /**
     * @return 大根堆中最大值
     */
    public int pop () {
        if (this.heapSize == 0) {
            throw new RuntimeException("heap is empty");
        }
        int temp = this.arr[0];

        /*最后一个位置的值和 0 位置交换
        * 堆大小-1, 最后一个位置无论是什么数和堆无关*/
        SwapUtil.swap(this.arr, 0, --heapSize);

        heapify(arr, 0, heapSize);

        return temp;
    }

    /**
     *
     * @param arr 存放堆数据的数组
     * @param index 从当前位置往下比较
     * @param heapSize 堆的大小，避免越界
     */
    private void heapify(int[] arr, int index, int heapSize) {
        /*从零开始做跟孩子做比较，直到叶子节点或者比较完不用交换了*/
        int leftChildIndex = (index << 1) | 1;
        while (leftChildIndex < heapSize) {//说明还有孩子结点

            int largerChildIndex = leftChildIndex;
            int rightChildIndex = leftChildIndex + 1;
            if (rightChildIndex < heapSize) {//有右孩子
                largerChildIndex = arr[leftChildIndex] > arr[rightChildIndex] ? leftChildIndex : rightChildIndex;
            }

            // 根结点要满足当前子树最大，如果不满足，需要交换
            if (arr[index] < arr[largerChildIndex]) {
                SwapUtil.swap(arr, index, largerChildIndex);
                index = largerChildIndex;
                leftChildIndex = (index << 1) | 1;
            } else {// 当前子树已经满足大根堆，不用再往下比较了
                break;
            }

        }
    }

    @Override
    public String toString() {
        return "MaxHeap{" +
                "heapSize=" + heapSize +
                ", limit=" + limit +
                ", arr=" + Arrays.toString(arr) +
                '}';
    }
}